The development of software products is a time-consuming, detail oriented, and resource intensive process. One important aspect of this process is the testing of software by executing the software to determine errors in the program or application. The object of testing is to verify the proper functioning of the software. In a typical testing program, test data is used to determine whether the program is functioning properly. One of the challenges presented by software testing is that the number of errors in a software program may be quite large and difficult to detect. To find potential errors; a test engineer may be required to devise complicated test cases and systematic exploration of the value domains for test data. Numerous methodologies have been employed in the testing of software.
One way of testing the software is to write a plurality of test cases for the software. A test case is typically a sequence of actions implemented by the software being tested and associated with the required inputs and desired outputs to identify an error in the software. The collection of test cases is usually referred to as test suite. Typically the objective of the test suite is to determine whether the software implementation conforms to the specification for the software. It is common for test suites to be created and applied during the development of the software products. One methodology is to enter the test data manually using an input device. This methodology has the disadvantage of being time-consuming, expensive, and susceptible to data entry mistakes. Another methodology is to automate the generation of test data for each test case. For example, the software under test may be modeled as a finite state machine that includes states and transitions between states. Information specifying when a transition is to be implemented and the effect of implementing the transition is also included. One of the difficulties of implementing automated testing programs is that the number of test cases may grow to a very large number, making the implementation of the tests time-consuming and resource and intensive.
These problems are compounded when testing large, complex, virtual machines. As used here, a virtual machine is software that isolates the application being used by the user from the computer. Versions of the virtual machine are written for various computer platforms, consequently any application written for the virtual machine can be operated on any of the platforms. Commonly used techniques for testing of virtual machines have a number of disadvantages. One drawback is that they typically operate on abstract models of the code and not actual implementation. Another disadvantage is that the testing only covers a subset of the constructs found in the virtual machine, and necessitates manual efforts to map the formal model onto the implementation. Techniques such as directed test case generation have been commonly used by virtual machine developers. Those manual testing techniques end up being expensive and slow due to the amount of human effort they entail.
Automatic test generation systems have been implemented where the coverage levels of tests are controlled by trading loss between the thoroughness of the test and the amount of time required to execute the test. One way in which this is been accomplished is to model the system under test as a finite state machine made up of interconnected models. The coverage level of each model is controlled to avoid generating paths that differ only by just that had been already concluded in other paths.
Enhanced context free grammars have been used as a means for generating test data. Such grammars may be used to create random samples of tests as well as to create complete tests. Production grammars have also been used for test generation. Production grammars can generate a variety of test cases and how those test cases should behave. These grammar based testing methodologies utilize stochastic test data generation. The generally accepted approach is to annotate a grammar with probabilistic weights on the productions and other hints. A test-data set is then generated using probabilistic production selection and potentially further heuristics. Stochastic approaches have been successfully applied to practical problems. The problem with these existing approaches is that they do not clearly quantify the degree of coverage achieved by the resulting test data. As long as randomized test-data generation is done in a pure manner, one may potentially refer to stochastic arguments when attempting the quantification of coverage. However, most practical test problems for meta-data-driven functionality require more control on the generation process.
For instance, randomized generation may need to be mixed with pair-wise testing in a certain way, or ingenious weights must be designed by the tester to make test-data generation terminate, or to express intents of coverage. Some state-of-the-art testing approaches do indeed provide some control mechanisms to this end. However, such control efforts make it even more difficult to obtain a clear understanding of coverage. The problem is basically that existing approaches lack a principled model for the suite of control mechanisms, which makes it difficult to apply them and anticipate their effect.
To summarize, current approaches for testing meta-data-driven functionality lack a fundamental and general notion of coverage, and they tend to provide suites of control mechanisms with ad-hoc justification and complex operational semantics.